A typical prior art computer network allows connected computers to communicate by exchanging data packets. Two important classes of such networks are connection-oriented and connectionless packet-switching networks.
Connection-oriented technology is based on a notion of establishing a virtual connection across the network between communicating computers, the same way telephone connections are established. This approach makes packet routing very simple, requiring a single look-up in an array, so it can be implemented in high-speed circuitry. The connection-oriented approach is the basis of a technology known as Asynchronous Transfer Mode (ATM).
Although the connection-oriented technology allows very high speeds in packet forwarding, the process of establishing and tearing down connections remains a major limitation. For example, despite the very high aggregate throughput of conventional digital telephony systems, they are nearly useless for global data communications which generally require a network to be able to sustain connection establishment rates in excess of 10 connections per second per client computer.
The second technology, a connectionless network, provides only best-effort delivery of data packets, routing every packet separately step-by-step to its ultimate destination. This scheme is analogous to a postal service, whereby every message is delivered to its recipient by the address, but sorting centers do not keep track of who communicates with whom. The connectionless packet switching technology is the basis of TCP/IP, the set of protocols defining the Internet.
Obviously, connectionless packet switching does not have connection establishment rate limitations. However, the process of finding the appropriate next step for routing a packet by the packet's destination address is non-trivial and generally cannot be implemented in very high-speed circuitry. Therefore, existing commercial IP routers have relatively low throughput.
Virtual connections in connectionless networks are identified with source and destination host addresses expanded with source and destination port numbers within those computers, to permit multiple concurrent connections between the hosts. An important feature of modem host TCP/IP implementations is that they expect packets sent into the network to be received in the same order. Violation of packet ordering causes false detection of packet loss by the fast retransmission algorithm, thus significantly degrading network performance.
FIGS. 1A and 1B illustrate architectures of existing IP routers. FIG. 1A shows the architecture of a router by Cisco Systems, whereby all packets arriving to the router have to traverse a shared system bus 30, after being processed by interface processors 31. A central processor 32 controls operation of interface processors 31 and performs routing of non-typical data packets which cannot be completely processed by the interface processors. The bus throughput severely limits the router's aggregate throughput. Moreover, the bus and the central processor are single points of failure; therefore the reliability of such routers is also somewhat limited.
FIG. 1B shows a more advanced IP routing technology by NetStar, whereby the shared bus is replaced with a crossbar switch 33. Crossbar switch 33 allows much greater aggregate throughput, but the throughput per attached line remains limited. Moreover, crossbar switches are not scalable and are limited by the speed of scheduling circuitry.
In U.S. Pat. No. 5,274,631 to Bhardwaj (1993), a packet switch built with a plurality of packet processors and a multiplexing means would allow greater aggregate throughput, but the preferred embodiment is described as not scalable. Also, the described apparatus is unable to perform IP routing (an OSI reference model Level 3 operation) since it is designed to perform Ethernet packet switching (a Level 2 operation).
U.S. Pat. No. 5,537,403, U.S. Pat. No. 5,550,815 and U.S. Pat. No. 5,554,160, all to Cloonan and Richards (1996), U.S. Pat. No. 5,469,433 to McAuley (1995) and U.S. Pat. No. 5,303,232 to Proctor et al. (1994), all describe parallel apparata for very high speed ATM (connection-oriented) packet switching. However, none of these address the issue of connection establishment rates as a limitation to the overall packet router performance, nor do they improve per-line throughput.
A number of related prior art works relate to the data interconnect part of the present invention and can be therefore be incorporated to achieve further improvements: U.S. Pat. No. 5,191,578 to Lee (1993), U.S. Pat. No. 5,175,733 to Nugent (1992), U.S. Pat. No. 5,218,676 to Ben-Ayed and Merriam (1993), U.S. Pat. No. 5,404,562 to Heller and Oliveau (1995), U.S. Pat. No. 5,345,556 to Zapisek (1994), U.S. Pat. No. 5,226,125 to Balmer et al. (1993), U.S. Pat. No. 5,247,694 to Dahl (1993), and U.S. Pat. No. 4,598,400 to Hillis (1986), all. However, those works are neither necessary nor sufficient for achieving the objects and advantages of the present invention.